The present invention relates generally to data communication and, more particularly, concerns a method and apparatus for decoding signals of variable data rates that have been previously encoded with a Reed Solomon (RS) code.
Reed Solomon Codes are a ubiquitous class of error correcting codes, employed in various types of communication systems, for example, fiber optic systems and HDTV applications. Due to their wide applicability, RS encoders and decoders are employed in several different scenarios, characterized by differing resource constraints, input data rates, and error correction abilities. Optimizing an RS implementation strongly depends on the usage scenario.
An RS code is characterized by the following parameters, m and t, where m is the length of a single data word and t is the maximum number of errors that can be corrected. The total length of the code block is 2m−1, of which 2t words are parity words and 2m−1−2t words are a copy of the original message.
RS decoding proceeds in five distinct steps:                Syndrome computation: In this step, the 2t syndrome words are computed from the received code word, r1, r2, . . . , rn using the following formula:        
                                          s            i                    =                                    ∑                              j                =                1                            n                        ⁢                                                  ⁢                                          r                j                            ⁢                              α                i                j                                                    ,                              i            ∈                          {                              1                ,                2                ,                3                ,                …                ⁢                                                                  ,                                  2                  ⁢                  t                                            }                                =                                    ∑                              j                =                1                            n                        ⁢                                                  ⁢                                          r                j                            ⁢                              X                j                i                                                    ,                                  ⁢                              where            ⁢                                                  ⁢                          X              j                                =                      α            j                                              (        1        )                            Error locator polynomial computation: The error locator polynomial, Λ, has degree t, and its roots are given by a α−j where j corresponds to an error location. Λ(z)=1+σ1z+σ2z2+ . . . +σtzt         Error evaluator polynomial computation: The error evaluator polynomial, Ω, has t-1 roots and is used in a formula to compute the magnitude of the error once the location of an erroneous word is known.        Error location: Once the error locator polynomial is known, each of 2m−1 possible error locations is tried out as a potential error location by evaluating the Λ(α−j), jε{1,2, . . . ,255}. A maximum of t error locations are identified.        Error correction: For each of the identified error location, the magnitude of the error is calculated according to the following formula: ek=α−kΩ(α−k)/Λ′(α−k), and the kth received word is corrected according to the formula: rk=rk+ek         